package 二叉树的最近公共祖先;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 二叉树的最近公共祖先
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *   这道题需要采用后序遍历，找到最深的节点
 *   采用递归方式，题目本身就是递归函数
 * @date 2022/11/7 10:00
 */
public class Demo236 {


    //Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    //递归三部曲
    //1.确定参数和返回值
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //2.返回条件
         if(root==null||root.val== p.val||root.val== q.val){
             return root;
         }
         //3，开始遍历
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        //4。中间节点逻辑处理
        if(left!=null&&right!=null){
            //左右子树都能搜到，返回root即为祖先
            return root;
        }
        //右子树为空，左子树不为空，说明左节点就是父节点
        if(right==null&&left!=null){
            return left;
        }
        //左子树为空，右子树不为空，说明右节点就是父节点
        if(left==null&&right!=null){
            return right;
        }
        return null;

    }

}
